package recursion

import problem.Problem

class Q119PascalsTriangleII extends Problem {

  def getRow(rowIndex: Int): List[Int] = {
    val a = new Array[Int](rowIndex + 1)
    a(0) = 1
    val b = new Array[Int](rowIndex + 1)
    b(0) = 1
    update(0, rowIndex, a, b).toList
  }

  def update(r: Int, n: Int, p: Array[Int], c: Array[Int]): Array[Int] = {
    if (r == 0) update(r + 1, n, p, c)
    else if (r > n) p
    else {
      (1 to r).foreach { j =>
        c(j) = f(j, r, p)
      }
      println(s"i = $r, n = $n, ${c.toList}")
      update(r + 1, n, c, p)
    }
  }

  def f(j: Int, n: Int, p: Array[Int]): Int = {
    if (j == 0 || j == n) 1
    else p(j - 1) + p(j)
  }

  override def test(): Unit = {
    getRow(0) should contain theSameElementsInOrderAs (List(1))
    getRow(1) should contain theSameElementsInOrderAs (List(1, 1))
    getRow(2) should contain theSameElementsInOrderAs (List(1, 2, 1))
    getRow(3) should contain theSameElementsInOrderAs (List(1, 3, 3, 1))
    getRow(4) should contain theSameElementsInOrderAs (List(1, 4, 6, 4, 1))
  }
}
